This invention relates to logic circuits, and more specifically to a Mealy or Moore type synchronous sequential state machine.
A state machine cycles through a sequence of possible states, dependent upon decision variable signals input to the state machine during successive states. Referring to FIG. 1, a simplified prior art state machine 2 includes a combinatorial logic network 4 (for example, a memory) and a feedback register 6. Signals received at (for example, memory address) input terminals 3 are transformed in combinatorial logic network 4, which is configured according to a user-supplied sequential function, to produce state word output signals at network 4 output terminals 5. The "present state" of state machine 2 is defined by the value of the state word output signals, comprised of data signals, which are applied through buffer 8 to state machine output lines 9, and feedback signals, which are transferred through timed register 6 to feedback lines 7. Present state feedback signals generally change the values of signals input to terminals 3 of logic network 4, and thereby causing the state machine to undergo a transition from its present state to its "next state". Next state transitions are determined as a function of one or more present state feedback signals, either conditionally with decision variables received from external devices (not shown), or unconditionally independent of decision variable conditions.
Synchronous sequential state machines are distinguished as Mealy type machines, in which, referring to FIG. 1, network 4 output data signals pass immediately through buffer 8 to state machine output terminals 9, and thus are determined by present conditions or values of decision variables at network input terminals 3, or as Moore type machines, in which network 4 output data signals are delayed at the input terminals of buffer 8 (which may be equivalent to timed feedback register 6) until the next period of timing signal CLK, when data signals are transferred to state machine output terminals 9. Thus, Moore machine data outputs are determined by previous decision variable input conditions.
Synchronous sequential type state machines execute ongoing sequences, without ending states, and, while supplied with power, can only "stop" by circling through states in a loop, either endlessly, for example in an "error trap," or until a decision variable input condition changes and branches the state machine to a new state, outside of the loop. Synchronous sequential state machines (or "sequencers") are commonly used, for example, as small controllers to drive industrial machinery, in computer systems to manage communication buses, memories, or peripheral devices, or to encode or decode data.
The capabilities of a sequencer circuit are determined by its input capacity (i.e. the number of input decision variables it receives from external devices), output capacity (i.e. the number of data output signals it provides to external devices), feedback capacity (i.e. the number of feedback variables), number of states, and state transition or branching capabilities, speed, and efficiency. Small arbitration controllers (used for example to arbitrate access to a single communication bus by one of several devices) typically execute sequences of from 3 to 40 states, each state capable of branching to a next state among a typical maximum of up to 16 possible next states.
The uses of a sequencer formed as an integrated circuit (IC) are limited by the availability of input and output (I/O) terminals. A limited-output sequencer may only be able to implement certain functions by supplying encoded data signals, which are decoded by an external circuit to provide the desired data output signals. Similarly, decision variable input capacity of the sequencer limits the number of conditions for branching. Decision variable signals may have to be encoded before application as input signals to a limited-input sequencer. Externally encoding decision variable input signals and/or decoding data output signals through other circuits increases the size, power, complexity, and cost, and decreases the speed, of a sequencer. Therefore it is preferable to have a large decision variable input capacity.
Decision variable input signals can be transformed by a combinatorial logic network 4 comprising an addressable memory, which is enabled to output state words. A set of N binary decision variables has a range of 2.sup.N values or combinations, each combination's values potentially representing a distinct decision variable input condition, which determines the transition or branch to the next state, or address of one of 2.sup.N state word memory locations. However, practical sequencers which test N decision variables commonly have no state transition dependent upon all N variables. Instead, the maximum number of decision variables relevant to any one state transition is Rmax. This leaves at least N-Rmax=D irrelevant decision variables for every state transition, which are evaluated by an address decoder branching to a different memory location, which must store the same state word value, for each of the 2.sup.D irrelevant variable combinations possible with each combination of the Rmax relevant variables. Thus, a sequencer using an N bit address decoder wastes at least 2.sup.N -2.sup.Rmax state word memory locations for each state transition.
This waste of state word memory capacity is avoided in prior art sequencers using feedback signals controlling multiplexers (MUXs) to select only Rmax decision variables for use in determining the address in a state word memory containing the next state word. In this event, to form a next state address for a state having less than Rmax relevant decision variables, the MUX must also select one or more irrelevant decision variables to complete the Rmax bit address. Rmax decision variable input signals have a range of 2.sup.Rmax values or addresses. However, typical sequences include many states in which one or more sets of several decision variable conditions yield the same next state branch or branches, and for any state in the sequence, even those states with Rmax relevant decision variables, the maximum number of sets of input conditions, or actual branches Amax, is no more than 2.sup.Rmax-P, for a positive integer P&lt;Rmax. In this event, the actual branch condition sets can be mapped onto, or relabelled by, C=Rmax-P new binary variables, requiring only 2.sup.C state word memory address locations for defining the possible next state branches from any present state.
Still, unconditional, and many conditional, next state transitions require fewer than Amax=2.sup.C branch addresses. In prior art sequencers, despite reducing the 2.sup.N possible decision variable combinations, by selecting only Rmax decision variable input lines, and by mapping branch condition sets onto only C bit branch addresses, state word memory addresses reserved for, but not used by, states with less than 2.sup.C possible next states, are wasted.
NASA Tech Brief Vol. 9, No. 2, Item 36 describes a sequencer which minimizes the number of next state addresses committed to each state by using feedback signals controlling a multiplexer to select only one decision variable input line from among N decision variable lines, for two-way branching in each state. The NASA sequencer can execute a "branch fan-out tree" to use R&gt;1 decision variables serially, in R cycles, each cycle branching to one of a possible E=2 intermediate states, for branching to one of a total of T=E.sup.R possible next states. Each of the R cycles is, in effect another intermediate state, lengthening and delaying the sequence.
The proposal in "Word Reduction in Microprogrammed Controllers" pp. 161-173 of Microprocessing and Microprogramming No. 9, North-Holland Publishing Co. (1982), by Ditzinger and Beister, describes a circuit which uses two multiplexers to each select a decision variable input signal for 2.sup.Rmax =4 way branches in each state. Either of the multiplexers can be forced to select a fixed logical 1 or logical 0 input signal, thus reducing the number of bits, and the effective range, of the branch address signal. However, the use of MUXs severely limits the choice of decision variable combinations for providing branch conditions.
A single branch address can be formed for each set of decision variable conditions through the use of more elaborate circuits such as AMD, Inc., No. Am2910 controllers, or larger computer systems. The AMD controllers use a fixed (in contrast to programmable) logic configuration which is set up by micro-programmed instructions for each state to generate addresses. The AMD sequencers are unnecessarily complex for many small state machine implementations, and their decision variable input capacity is limited.
Signetics Inc. sequencer No. 82S105 avoids reserving for each state a constant number 2.sup.C of branch addresses to be transformed by the combinatorial logic network, by using, instead of an address-decoder memory, a programmable logic array (PLA) in which, for each state, each combination of decision variable lines for each branch condition is connected, within the PLA, to the input leads of a respective product term AND gate. Product term AND gates specifically programmed for each branch condition are able to select just one next state address for each actual branch, in one mapping step, eliminating the need for an input selection circuit which selects only Rmax input decision variables before the mapping step. In each state, at least one true decision variable condition enables its associated AND gate to provide a high product term output signal, which is applied through programmed connections to selected OR gates to generate a state word output signal.
The 82S105 PLA-based sequencer can be programmed conveniently to enable any of its 48 product terms on any given combination of feedback and decision variable input signals, but it executes sequences only up to 48 states. However, sequencers in practice often require Amax equal to only a fraction of 48 branches. While a given decision variable condition is commonly used for branching from several states, in each state distinct branch addresses may need to be formed by a respective programmable input product term, which is costly, consumes more power, and requires more area in an integrated circuit. Software support capability to compile a state machine description, and to minimize the number of feedback signals and product terms, is limited, and it is not routinely evident whether a given PLA can implement a given sequential function.
Various algorithms are known for minimizing the number of states and branches in a sequence, but no ideal algorithm is known for forming branch addresses independently of the next state primary address, while making substantially complete use of an address decoder memory. There remains, therefore, a need for a sequencer in the form of a single integrated circuit which is simple and flexibly programmable to map decision variable input conditions onto actual branch addresses independently of the present state, and to make better use of state memory, and to do this for sequences having many states with few branches or for sequences having few states with many branches.